import java.util.Random;

public class test6 {
    static char[] tmp;

    public static void main(String[] args) {
        char[] arr = {'e','g','z','g','a'};
        int[] arr2 = {10,9,8,7,6,5};
//        quickSort(arr,0,arr.length-1);
        tmp = new char[arr.length];
        mergeSort(arr,0,arr.length-1);
        for(char ch:arr){
            System.out.print(ch+" ");
        }
    }
    //快速排序字符数组
    public static void quickSort(char[] arr,int l,int r){
        if(l>=r){
            return;
        }
        Random random = new Random();
        int index = random.nextInt(r-l+1)+l;
        char key = arr[index];
        int left = l-1,right = r+1,i=l;
        while (i<right){
            if(arr[i]<key){
                swap(arr,++left,i++);
            }else if(arr[i]==key){
                i++;
            }else{
                swap(arr,--right,i);
            }
        }
        quickSort(arr,l,left);
        quickSort(arr,right,r);
    }
    //归并排序
    public static void mergeSort(char[] arr,int left,int right){
        if(left>=right) return;

        int mid = (right+left)/2;
        System.out.println("mid:"+mid);
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);

        int cur1 = left,cur2 = mid+1,i = 0;
        while(cur1<=mid && cur2<=right){
            if(arr[cur1]<=arr[cur2]){
                tmp[i++] = arr[cur1++];
            }else{
                tmp[i++] = arr[cur2++];
            }
        }
        while (cur1<=mid){
            tmp[i++] = arr[cur1++];
        }
        while (cur2<=right){
            tmp[i++] = arr[cur2++];

        }
        for(int j = left;j<=right;j++ ){
            arr[j] = tmp[j-left];
        }


    }

    public static void swap(char[] arr,int a,int b){
        char temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
